# include <iostream>
using namespace std;
/*图的相关定义*/
#define MAX_VERTEX_NUM 100
#define INFINITY 65535 // 表示无穷大
typedef struct ArcNode{
    int adjVex; //所（被）指向的“顶点”节点在邻接数组中的索引
    struct ArcNode * next; //指向同一顶点对应的下一条“边”节点
    int weight; //边的权重
}ArcNode;
typedef int VertexType;
typedef struct VexNode{
    VertexType data; //顶点数据
    ArcNode * firstArc; //指向链表中的第一个“边”结点
}VexNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
    AdjList vertices;//所有节点与节点之间的关系
    int vexNum;//总的节点数
    int arcNum;//总的弧数
    int kind;//图的类型
}ALGraph;


/*
  迪杰斯特拉算法：
    算法思想：迪杰斯特拉算法是一种用于求解单源最短路径问题的贪心算法。其基本思想如下：
    1.创建两个数组，一个用于记录顶点的最短距离，另一个用于记录顶点是否已经被访问过。
    2.初始化起点的最短距离为0，其他顶点的最短距离为无穷大。将起点标记为已访问。
    3.对于起点相邻的顶点，更新其最短距离为起点到该顶点的边权重，并标记为已访问。
    4.在未访问的顶点中找到距离起点最近的顶点，将其标记为已访问。
    5.更新所有与该顶点相邻的未访问顶点的最短距离，如果通过该顶点到达某个未访问顶点的距离更短，则更新最短距离。
    6.重复步骤4和步骤5，直到所有顶点都被访问过或者没有可以访问的顶点为止。
    7.最终得到起点到每个顶点的最短距离。
 */
// 迪杰斯特拉算法
void Dijkstra(ALGraph G, int start) {
    int visited[MAX_VERTEX_NUM]; // 标记顶点是否已访问
    int dist[MAX_VERTEX_NUM]; // 存储起点到各个顶点的最短距离

    // 初始化visited和dist数组
    for (int i = 0; i < G.vexNum; i++) {
        visited[i] = 0;
        dist[i] = INFINITY;
    }

    visited[start] = 1;
    dist[start] = 0;

    // 遍历邻接链表，更新距离
    ArcNode* p = G.vertices[start].firstArc;
    while (p != NULL) {
        dist[p->adjVex] = p->weight;
        p = p->next;
    }

    // 开始主循环
    for (int i = 1; i < G.vexNum; i++) {
        int minDist = INFINITY;
        int minIndex = -1;

        // 找到距离起点最近的未访问顶点
        for (int j = 0; j < G.vexNum; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        if (minIndex == -1) // 未找到可达顶点，退出循环
            break;

        visited[minIndex] = 1;

        // 更新距离数组
        ArcNode* p = G.vertices[minIndex].firstArc;
        while (p != NULL) {
            if (!visited[p->adjVex] && dist[minIndex] + p->weight < dist[p->adjVex]) {
                dist[p->adjVex] = dist[minIndex] + p->weight;
            }
            p = p->next;
        }
    }

    // 输出最短路径
    printf("起点到各个顶点的最短距离为：\n");
    for (int i = 0; i < G.vexNum; i++) {
        printf("顶点 %d 的最短距离为 %d\n", i, dist[i]);
    }
}




//测试
int main(){



    return 0;
}